package features.advance.leetcode.tree.easy;

import features.advance.leetcode.tree.model.TreeNode;
import features.advance.leetcode.util.TreeUtil;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author LIN
 * @date 2022-06-29 14:39
 *  145. 二叉树的后序遍历
 *
 *  难度：简单
 *
 * 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [1,null,2,3]
 * 输出：[3,2,1]
 * 示例 2：
 *
 * 输入：root = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：root = [1]
 * 输出：[1]
 *
 *
 * 提示：
 *
 * 树中节点的数目在范围 [0, 100] 内
 * -100 <= Node.val <= 100
 *
 *
 * 进阶：递归算法很简单，你可以通过迭代算法完成吗？
 */
public class Solution145 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
            /**
             * Morris遍历
             * @param root
             * @return
             */
            @Override
            public List<Integer> postorderTraversal(TreeNode<Integer> root) {
                List<Integer> res = new ArrayList<Integer>();
                if (root == null) {
                    return res;
                }

                TreeNode p1 = root, p2 = null;

                while (p1 != null) {
                    p2 = p1.left;
                    if (p2 != null) {
                        while (p2.right != null && p2.right != p1) {
                            p2 = p2.right;
                        }
                        if (p2.right == null) {
                            p2.right = p1;
                            p1 = p1.left;
                            continue;
                        } else {
                            p2.right = null;
                            addPath(res, p1.left);
                        }
                    }
                    p1 = p1.right;
                }
                addPath(res, root);
                return res;
            }

            public void addPath(List<Integer> res, TreeNode<Integer> node) {
                int count = 0;
                while (node != null) {
                    ++count;
                    res.add(node.val);
                    node = node.right;
                }
                int left = res.size() - count, right = res.size() - 1;
                while (left < right) {
                    int temp = res.get(left);
                    res.set(left, res.get(right));
                    res.set(right, temp);
                    left++;
                    right--;
                }
            }
        };
//        TreeNode<Integer> root = new TreeNode<>(3,new TreeNode<>(2),new TreeNode<>(4,new TreeNode<>(1),null));
        String input = "[3,2,4,null,null,1]";
        input = "[3,9,4,null,null,5,7]";
        TreeNode<Integer> root = TreeUtil.stringToTreeNode(input);
        List<Integer> integers = solution.postorderTraversal(root);
        System.out.println(integers);

    }

    static class Solution {
        public List<Integer> postorderTraversal(TreeNode<Integer> root) {
            List<Integer> res = new ArrayList<Integer>();
            if (root == null) {
                return res;
            }

            Deque<TreeNode> stack = new LinkedList<TreeNode>();
            TreeNode<Integer> prev = null;
            while (root != null || !stack.isEmpty()) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                if (root.right == null || root.right == prev) {
                    res.add(root.val);
                    prev = root;
                    root = null;
                } else {
                    stack.push(root);
                    root = root.right;
                }
            }
            return res;
        }
    }
}
